/*
 * @Date: 2019-08-31 14:45:27
 * @Github: https://github.com/FinnWu
 * @LastEditors: Finnwu
 * @LastEditTime: 2019-08-31 14:54:56
 */


// 斐波那契数列的第n项
var map = {}
function Fibonacci(n){
    // write code here
    if(n == 0 || n == 1) {
        return n
    }
    if (map[n]) {
        return map[n]
    }
    map[n] = Fibonacci(n - 1) + Fibonacci(n - 2)
    return map[n]
}

function Fibonacci2(n) {
    if(n == 0 || n == 1) {
        return n
    }
    var pre = 0
    var next = 1
    for (var i = 2; i <= n; i++) {
        var temp = next
        next = pre + next
        pre = temp
    }
    return next
}


console.log(Fibonacci(3));
console.log(Fibonacci(4));
console.log(Fibonacci(5));

console.log(Fibonacci(2));
console.log(Fibonacci(3));
console.log(Fibonacci(4));
